package com.gofaraway.service.student.leetcode;

import org.apache.commons.lang3.StringUtils;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author ChenPeng
 * @Date 2024/9/14 15:01
 */
public class Demo12 {


    /**
     * 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     *
     * @param s
     * @param t
     * @return
     */
/*    public String minWindow(String s, String t) {

        //滑动窗口  指定 两个指针 两个指针间隔始终一致
        if (StringUtils.isBlank(s)|| StringUtils.isBlank(t)) {
            return "";
        }

        //窗口大小
        int size = t.length();

        int pre = 0;
        int before = pre + size - 1;

        char[] array = s.toCharArray();

        while (before < s.length() -1) {

            s.substring(pre, before).toCharArray();
            if ()
            pre++;
            before++;
        }
    }*/

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        // 初始化need哈希表
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0; // 当前窗口符合要求的字符个数
        int start = 0; // 记录符合条件的子串起始位置
        int length = Integer.MAX_VALUE; // 记录符合条件的子串长度

        while (right < s.length()) {
            char c = s.charAt(right);
            right++;

            // 更新window哈希表
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).intValue() <= need.get(c).intValue()) {
                    valid++;
                }
            }

            // 检查当前窗口是否有效
            while (valid == t.length()) {
                if (right - left < length) {
                    start = left;
                    length = right - left;
                }

                char d = s.charAt(left);
                left++;

                // 更新window哈希表
                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue()) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }

        return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);
    }

    public static void main(String[] args) {
        Demo12 solution = new Demo12();
        System.out.println(solution.minWindow("ADOBECODEBANC", "ABC")); // 输出 "BANC"
    }

}
